// 排序 时间复杂度 O(nlogn) 空间复杂度 O(logn)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 1) return intervals;
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ret;
        for (auto& data: intervals) {
            if (ret.empty()) {
                ret.emplace_back(data);
                continue;
            }
            if (data[0] > ret.back()[1]) {
                ret.emplace_back(data);
            }
            else {
                ret.back()[1] = max(ret.back()[1], data[1]);
            }
        }
        return ret;
    }
};